home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / mphf / support.c < prev    next >
C/C++ Source or Header  |  1993-04-08  |  4KB  |  169 lines
  1. /****************************  support.c  **********************************
  2.  
  3.    Purpose:    Provide some useful support routines:
  4.  
  5.                --    Storage allocators that exit on error (since this
  6.                 isn't a subroutine library, there's no need for
  7.             fancy error-handling).
  8.  
  9.             --    A routine to write the MPHF to a file.
  10.  
  11.             --    A routine to verify the correctness of a MPHF.
  12.  
  13.    Provenance:    Written and tested by Q. Chen and E. Fox, March 1991.
  14.            Edited and tested by S. Wartik, April 1991.
  15.  
  16.    Notes:    None.
  17. **/
  18.  
  19. #include <stdio.h>
  20.  
  21. #include "types.h"
  22.  
  23. #ifdef __STDC__
  24.  
  25. extern char    *malloc( unsigned int size );
  26. extern char    *realloc ( char *area, unsigned int size );
  27.  
  28. extern void    exit();
  29.  
  30. #else
  31.  
  32. extern char    *malloc(),
  33.         *realloc();
  34.  
  35. extern void    exit();
  36.  
  37. #endif
  38.  
  39. /*************************************************************************
  40.  
  41.     owncalloc( n, size )
  42.  
  43.   Return:    char * -- Pointer to a chunk of memory.
  44.  
  45.   Purpose:    Allocate a chunk of memory of 'n' elements each of size 'size'.
  46.         Return the pointer to the chunk.  Abort if no space is available.
  47. **/
  48.  
  49. char *owncalloc( n, size )
  50.     int        n,      /* in: number of elements.   */
  51.         size;   /* in: size of each element. */
  52. {
  53.     char    *temp;
  54.  
  55.     if ( (temp = malloc( (unsigned int)(n*size) )) == 0 ) {
  56.     fputs("Panic: cannot allocate memory.\n", stderr);
  57.     exit(1);
  58.     }
  59.     return(temp);
  60. }
  61.  
  62. /*************************************************************************
  63.  
  64.     ownrealloc( n, size )
  65.  
  66.   Return:    char * -- Pointer to a chunk of memory.
  67.  
  68.   Purpose:    Re-allocate a chunk of memory pointed to by area -- make it
  69.           new_size bytes.  Abort if no space is available.
  70. **/
  71.  
  72. char *ownrealloc( area, new_size )
  73.     char    *area;        /* in: area to re-allocate. */
  74.     int        new_size;    /* in: new size.        */
  75. {
  76.     char    *temp;
  77.  
  78.     if ( (temp = realloc( area, (unsigned)new_size )) == 0 ) {
  79.     fputs("Panic: cannot reallocate memory.\n", stderr);
  80.     exit(1);
  81.     }
  82.     return(temp);
  83. }
  84.  
  85. /*************************************************************************
  86.  
  87.     write_gfun( arcs, vertices, tbl_seed, spec_file )
  88.  
  89.   Return:    void
  90.   
  91.   Purpose:    Write the MPHF specification to a file
  92. **/
  93.  
  94. void
  95. write_gfun( arcs, vertices, tbl_seed, spec_file )
  96.     arcsType        *arcs;      /* in: the arcs.                              */
  97.     verticesType    *vertices;  /* in: the vertices.                          */
  98.     int            tbl_seed;   /* in: seed used to set up random number tables. */
  99.     char        *spec_file; /* in: name of the specification file.           */
  100. {
  101.     int        i;        /* Iterator through vertices.            */
  102.     FILE    *fp;        /* Handle for specification file.        */
  103.  
  104.     if ( (fp = fopen(spec_file, "w")) == NULL ) {
  105.        fprintf(stderr, "Can't create hashing specification file \"%s\".\n",
  106.                spec_file);
  107.        exit(1);
  108.     }
  109.  
  110.     fprintf(fp, "%d\n%d\n%d\n",
  111.            arcs->no_arcs, vertices->no_vertices, tbl_seed);
  112.     for ( i = 0; i < vertices->no_vertices; i++ )
  113.     fprintf(fp, "%d\n", vertices->vertexArray[i].g);
  114.  
  115.     fclose(fp);
  116. }
  117.  
  118. /*************************************************************************
  119.  
  120.     verify_mphf( arcs, vertices )
  121.  
  122.   Return:    int -- NORM if MPHF is correct, ABNORM if not.
  123.  
  124.   Purpose:    Verify the computed MPHF is indeed minimal and perfect
  125. **/
  126.  
  127. int verify_mphf( arcs, vertices )
  128.     arcsType     *arcs;                   /* in: the arcs.     */
  129.     verticesType *vertices;        /* in: the vertices. */
  130. {
  131.     int      i,
  132.         status = NORM,
  133.         hash;                /* Hash value of a key. */
  134.     char    *disk;               /* Hash table.          */
  135.  
  136.     disk = owncalloc( arcs->no_arcs, sizeof(char) );
  137.  
  138.     for( i = 0; i < arcs->no_arcs; disk[i++] = EMPTY );
  139.  
  140.     for ( i = 0; i < arcs->no_arcs; i++ ) {
  141.     hash = abs( arcs->arcArray[i].h0 +
  142.             vertices->vertexArray[arcs->arcArray[i].h12[0]].g +
  143.             vertices->vertexArray[arcs->arcArray[i].h12[1]].g
  144.           ) % arcs->no_arcs ;
  145.  
  146.     if ( hash < 0 ) {
  147.         fprintf(stderr, "Panic: negative hash value.\n");
  148.         status = ABNORM;
  149.         break;
  150.     }
  151.  
  152.     if ( disk[hash] == FULL ) {
  153.         fprintf(stderr, "Panic: hash entry collided at");
  154.         fprintf(stderr, " position %d by the %dth word!\n", hash, i);
  155.         status = ABNORM;
  156.         break;
  157.     }
  158.     else
  159.         disk[hash] =  FULL;
  160.     }
  161.  
  162.     free( (char *)disk );
  163.  
  164.     return(status);
  165. }
  166.  
  167.  
  168.  
  169.